package com.bupt.basic;

import java.util.ArrayList;
import java.util.List;

public class BasicAlgorithm {

	/**
	 * 二分搜索
	 * 
	 * @param a
	 * @param low
	 * @param high
	 * @param val
	 * @return
	 */
	public int binarySearch(int[] a, int low, int high, int val) {
		while(low <= high){
			int mid = (low + high)/2;
			if(val <= a[mid] ) {
				high = mid - 1;
			}else {
				low = mid + 1;
			}
		}
		return low;
	}
    public int majorityElement(int[] nums) {
        int pivot = 0;
        int size = 1;
        for(int i = 1; i< nums.length;i++){
            if(nums[i] == nums[pivot]) {
                size++;
            }else {
                size--;
                if(size == 0) {
                    i++;
                    pivot = i;
                    size++;
                }
            }
        }
        return nums[pivot];
    }
    
    public List<Integer> majorityElementII(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) return list;
        
        return list;
    }
}
